Міністерство освіти, науки, молоді та спорту
Вінницький національний технічний університет
Кафедра комп’ютерних наук
Лабораторна робота №4
З дисципліни «Математичні методи дослідження операцій»
Тема: Розробка алгоритму та програми для розв’язування спеціальних
задач лінійного програмування (транспортна задача)
Мета: набути практичних навичок побудови опорного плану транспортної задачі різними методами та приведення його до оптимального методом потенціалів, а також програмної реалізації розв’язання транспортної задачі (ТЗ).
Хід роботи
Відповідно до варіанту 1.13 практично розв’язати транспортну задачу:
/
побудувати опорний план ТЗ трьома методами (методом північно-західного кута, методом мінімальної вартості, методом апроксимації Фогеля);
обрати опорний план, значення Fi якого є найменше;
перевірити побудований опорний план на оптимальність методом потенціалів;
якщо опорний план не є оптимальним, то за допомогою методу потенціалів будуємо оптимальний план;
якщо опорний план є оптимальним, то беремо відмінний від нього опорний план і застосовуючи метод потенціалів приводимо його до оптимального.
Розробити алгоритм та програму для розв’язання ТЗ. Було розроблено програму для реалізації методу подвійної позначки. Блок-схема алгоритму програми наведена далі:
Рисунок 1
Блок-схема алгоритму розв’язування ТЗ методом подвійної позначки.
Для тестування програми були введені дані з практичного завдання, результати виконання програми наведені далі:
/
Рисунок 2 – Результати тестування програми
/
Рисунок 3 – Результати тестування програми
/
Рисунок 4 – Результати тестування програми
Висновок: У ході виконання даної роботи, були набуті практичні навички побудови опорного плану транспортної задачі різними методами та приведення його до оптимального методом потенціалів, а також програмної реалізації розв’язання транспортної задачі (ТЗ). Було практично розв’язано транспортну задачу відповідного варіанту, розроблена програма для вирішення закритої транспортної задачі методом мінімального елемента. При тестуванні програми використовувалась задача з практичного завдання – відповіді зійшлись, отже програма працює правильно.
Додаток 1 – Інструкція користувача
Запустити програму RTZMP.exe;
/
Ввести к-ть постачальників і потреб., і натиснути ОК
/
Далі заповнити необхідні поля.
/
Вибрати метод і натиснути «Расчет»
Додаток 2 – Лістинг програми
static void DoubleMarkMethod(int[,] tarif, int[] amount, int[] needs, int providers, int customers)
{
Console.WriteLine("Метод подвійної позначки:\n");
//Вивід транспортної таблиці:
Console.WriteLine("\nтранспортна таблиця");
Console.WriteLine("prov / cust | B1 | B2 | B3 | amount |");
for(int i = 0; i < providers; i++)
{
Console.Write("A{0, -11:N0}|", i+1);
for(int j = 0; j < customers; j++)
{
Console.Write("{0, -4:N0}|", tarif[i, j]);
}
Console.Write("{0, -8:N0}|\n", amount[i]);
}
Console.Write("needs |");
for(int i = 0; i < customers; i++)
{
Console.Write("{0, -4:N0}|", needs[i]);
}
//
int[,] markTable = new int[providers, customers];
int[] needsSatisfy = new int[customers];
Array.Copy(needs, needsSatisfy, needs.Length);
int[] amountSatisfy = new int[providers];
Array.Copy(amount, amountSatisfy, amount.Length);
int[,] result = new int[providers, customers];
int needsSum = 0;
for(int j = 0; j < customers; j++)
{
needsSum += needsSatisfy[j];
}
while(needsSum != 0)
{
for (int i = 0; i < providers; i++)
for (int j = 0; j < customers; j++)
if (markTable[i, j] != -1)
ma...
